package label.propagation;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

import graphic.Graph;

/**
 * @author ZhangyiA
 * @describe: 改进后的 LPA 方法，采用了节点重要性进行节点降序，固定节点更新顺序
 * 当一个节点邻居节点中出现了多个最大标签，计算标签的影响，获得最大影响标签
 *
 * (1) Initialize the unique label for each node in the network, for a given node x, Cx(0) = x.
 * (2) Calculate the node importance for each node , sort nodes in descending order of NI,
 * and generate an ordered sequence X = {x1, x2, ···, xn}, where NI(x1) ≥ NI(x2) ≥ ··· ≥ NI(xn).
 * (3) Set iteration number t = 1.
 *
 * (4) For each node x ∈ X, iteratively update the node label. In the iterative process, each
 * node uses the label with the largest importance of adjacent nodes as the label itself.
 * When the number of multiple labels in the adjacent node of the node i reaches the maximum value,
 * LPA_NI recalculates the influence of the labels that reach the maximum number, and selects the
 * most influential label to update node i.
 *
 * (5) If iteration number t = maxIter or the label of each node is the same as that of most of its
 * neighboring nodes, then the nodes with the same label are placed in the same community, and the
 * algorithm ends; otherwise, set t = t + 1 and go to step (4).
 *
 * @date 2021/07/16
 */

class Point{
    public int id ;
    public float influence;
    public Point(int id , float influence){
        this.id = id;
        this.influence = influence;
    }
}

public class NIBLPA implements Propagation{

    private Graph graph = null;
    private int colSum = 0;
    private final double ALPHA = 0.2; // alpha = {0.1 , 0.2 ... 1}
    private Point[] sequence;

    public NIBLPA(Graph graph){
        this.graph = graph;
    }

    @SuppressWarnings("Duplicates")
    // return community partition result , Map represent community label and each community includes social node
    public Map<Integer , ArrayList<Integer>> getLPACommunityPartitionResult(){
        computeVertexImportance(); // 首先要计算每个顶点自身的重要性
        System.out.println("class NIBLPA --> step2: getLPACommunityPartitionResult");
        System.out.println("<1>. compute each node import");
        System.out.println("\n<2>. start label propagation");
        Map<Integer , ArrayList<Integer>> community = new HashMap<>();
        int iter = 1;
        long starTime1 = System.currentTimeMillis();
        while(iter <= tao && labelPropagation()){
            System.out.println("the iter = " + iter + " have finished !");
            iter ++;
        }
        long endTime1 = System.currentTimeMillis();
        System.out.println("cost time = " + (endTime1 - starTime1) + " ms");

        // 获得划分后的结果
        for(int i = 0 ; i < graph.getNode_num() ; i ++){
            int label = graph.vertices[i].pre_com_label;
            ArrayList<Integer> list = community.containsKey(label) ? community.get(label) : new ArrayList<>();
            list.add(i);
            community.put(label , list);
        }
        return community;
    }

    // 返回按照顶点重要性降序
    public void computeVertexImportance(){
        sequence = new Point[graph.getNode_num()];
        for(int i = 0 ; i < graph.getNode_num() ; i ++){
            float influence = graph.vertices[i].degree;
            float tempSum = 0;
            for(int j = graph.head[i] ; j != -1 ; j = graph.edges[j].getNext()){
                int nei = graph.edges[j].getVertexTo(); // 节点 i 的邻居节点
                int kshell = graph.vertices[nei].kshell;
                int degree = graph.vertices[nei].degree;
                tempSum += kshell / (degree * 1.0);
            }
            tempSum *= ALPHA;
            sequence[i] = new Point(i , influence + tempSum);
            graph.vertices[i].verInfluence = influence + tempSum; // 每个顶点记录自身的 重要性
        }
        // 如果两个点的重要性相等就按照 顶点编号升序 ， 否则按照重要性降序
        Arrays.sort(sequence , (s1 , s2) -> {
            if(s1.influence == s2.influence)
                return s1.id - s2.id;
            else
                return s2.influence - s1.influence > 0.0 ? 1 : -1;
        });
    }

    // 传播结束的标志： 1. tao = maxIter  2. tao < maxItar 但是迭代一轮下来没有任何一个顶点的标签被修改，说明已经稳定，无需再继续迭代了
    public boolean labelPropagation(){
        boolean flag = false; // 是否提前结束的标志
        for(Point point : sequence){
            Map<Integer , ArrayList<Integer>> countLabel = new HashMap<>();
            for(int i = graph.head[point.id] ; i != -1 ; i = graph.edges[i].getNext()){
                int label = graph.vertices[graph.edges[i].getVertexTo()].pre_com_label; // 获得邻居的标签
                ArrayList<Integer> list = countLabel.containsKey(label) ? countLabel.get(label) : new ArrayList<>();
                list.add(graph.edges[i].getVertexTo());
                countLabel.put(label , list);
            }

            // 修改标签,
            if(countLabel.size() == 0) continue;
            int replaceLabel = getReplaceLabel(countLabel , point.id);
            if(replaceLabel != graph.vertices[point.id].pre_com_label){
                graph.vertices[point.id].pre_com_label = replaceLabel; // 当前标签需要被修改
                flag = true;
            }
        }
        return flag;
    }

    // 获得邻居出现标签次数最大的标签，如果多个标签出现次数最大，随机选取一个
    @SuppressWarnings("Duplicates")
    public int getReplaceLabel(Map<Integer , ArrayList<Integer>> countLabel , int id){
        int replaceLabel = 0;
        Map<Integer , ArrayList<Integer>> count = new HashMap<>(); // 统计每个标签出现的次数 ，检验最大标签出现的次数 ; 并保存了标签
        int maxSize = -1;
        for(Map.Entry<Integer , ArrayList<Integer>> entry : countLabel.entrySet()){
            int size = entry.getValue().size();
            maxSize = Math.max(size , maxSize);  // 记录标签出现最大的次数
            ArrayList<Integer> list = count.containsKey(size) ? count.get(size) : new ArrayList<>();
            list.add(entry.getKey());
            count.put(size , list);
        }
        if(count.get(maxSize).size() == 1){  // 最大的标签只有一个 , 返回该标签
            replaceLabel = count.get(maxSize).get(0);
        } else { // 重复的时候需要计算所有标签的影响，取最大的影响的标签  NIBLPA 提出的
            replaceLabel = getMaxInfluenceLabel(count.get(maxSize) , id);
        }
        return replaceLabel;
    }

    // 首先需要根据原始顶点查找邻居顶点 , 计算邻居顶点标签是最大标签的, 并累加 该顶点的 verInfluence / degree
    public int getMaxInfluenceLabel(ArrayList<Integer> labels , int id){
        Map<Integer , Float> labelInfluence = new HashMap<>();
        for(Integer label : labels){
            labelInfluence.put(label , 0.0f);
        }
        for(int i = graph.head[id] ; i != -1 ; i = graph.edges[i].getNext()){
            int to = graph.edges[i].getVertexTo();
            int label = graph.vertices[to].pre_com_label;
            if(labelInfluence.containsKey(label)){
                float sum = labelInfluence.get(label);
                sum += graph.vertices[to].verInfluence / graph.vertices[to].degree;
                labelInfluence.put(label , sum);
            }
        }
        float maxInfluence = 0.0f;
        int maxLabel = 0;
        for(Map.Entry<Integer , Float> entry : labelInfluence.entrySet()){
            if(entry.getValue() > maxInfluence){ // 如果多个标签都是最大，且影响相等，就选取最先出现的那个
                maxInfluence = entry.getValue();
                maxLabel = entry.getKey();
            }
        }
        return maxLabel;
    }

    // 计算每个顶点的 KShell 值
    public void calculatedKShell(){
        boolean[] vis = new boolean[graph.getNode_num()];
        for(int i = 0 ; i < graph.getNode_num() ; i ++){
            if(graph.head[i] == -1){ // 说明该顶点没有后续顶点
                graph.vertices[i].kshell = 0; // 孤立点
                vis[i] = true;
            }
        }
        int k = 1;
        // 第一层循环是修改 K-Shell 中 k 的值 , 当网络中没有小于等于 k 的节点时 , k = k + 1 ;
        while(true){
            colSum = 0 ;
            Map<Integer , Integer> rowSum = getAllRowSum(vis);
            if(colSum == 0){
                break;
            }
            while(true){
                ArrayList<Integer> satisfyK = findSatisfyK(k , rowSum);
                if(satisfyK.size() == 0) break; // 没有 出度小于 k 的当前层结束
                for(Integer nodeId : satisfyK) {
                    vis[nodeId] = true;
                    graph.vertices[nodeId].kshell = k;
                }
                rowSum = getAllRowSum(vis);
            }
            k ++;
        }
    }

    public Map<Integer , Integer> getAllRowSum(boolean[] vis){
        Map<Integer , Integer> rowSum = new HashMap<>(); // 根据顶点 , 统计每个顶点的出度 和
        for(int i = 0 ; i < graph.getNode_num() ; i ++){
            if(vis[i]) continue; // 相当于该顶点已被删除
            int count = 0;
            for(int j = graph.head[i] ; j != -1 ; j = graph.edges[j].getNext()){ // 统计所有的点的出度和
                if(!vis[graph.edges[j].getVertexTo()]){
                    count ++;
                }
            }
            colSum += count;
            rowSum.put(i , count);
        }
        return rowSum;
    }

    public ArrayList<Integer> findSatisfyK(int k , Map<Integer , Integer> rowSum){
        ArrayList<Integer> satisfyK = new ArrayList<>();
        for(Map.Entry<Integer , Integer> entry : rowSum.entrySet()){
            if(entry.getValue() <= k){
                satisfyK.add(entry.getKey());
            }
        }
        return satisfyK;
    }

}
